/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._21;

/**
 * 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * <p>
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._21
 * @ClassName: MergeTwoSortList
 * @Author: linyaonan
 * @Date: 2019/10/12 10:12
 */
public class MergeTwoSortList {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode resultList = new ListNode(0);
        dealwithList(resultList, l1, l2);
        return resultList.next;
    }

    private void dealwithList(ListNode result, ListNode l1, ListNode l2) {
        if (l1 == null) {
            result.next = l2;
            return;
        }
        if (l2 == null) {
            result.next = l1;
            return;
        }
        if (l1.val <= l2.val) {
            result.next = new ListNode(l1.val);
            dealwithList(result.next, l1.next, l2);
        } else {
            result.next = new ListNode(l2.val);
            dealwithList(result.next, l1, l2.next);
        }
    }

    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {

        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        ListNode r = new ListNode(-1);
        ListNode p = r;

        dd(p, l1, l2);

        return r.next;
    }

    private void dd(ListNode r, ListNode l1, ListNode l2) {
        if (l1 == null) {
            r.next = l2;
            return;
        }
        if (l2 == null) {
            r.next = l1;
            return;
        }

        if (l1.val <= l2.val) {
            r.next = new ListNode(l1.val);
            dd(r.next, l1.next, l2);
        } else {
            r.next = new ListNode(l2.val);
            dd(r.next, l1, l2.next);
        }
    }

    /**
     * 不使用递归进行合并有序链表
     *
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists3(ListNode list1, ListNode list2) {
        // 1. 特殊情况直接返回
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        // 2. 双指针合并

        // 构造一个假头
        ListNode p = new ListNode(-1);
        ListNode r = p;
        // 两个链表都有数值的情况
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                p.next = new ListNode(list1.val);
                list1 = list1.next;
            } else {
                p.next = new ListNode(list2.val);
                list2 = list2.next;
            }
            p = p.next;
        }
        // 一定是一个链表为空
        if (list1 == null) {
            p.next = list2;
        } else {
            p.next = list1;
        }

        return r.next;

    }
}
